package gpeerreview.client;

import com.google.gwt.core.client.EntryPoint;
import com.google.gwt.user.client.Window;
import com.google.gwt.user.client.ui.Button;
import com.google.gwt.user.client.ui.ClickListener;
import com.google.gwt.user.client.ui.RootPanel;
import com.google.gwt.user.client.ui.Widget;
import com.google.gwt.user.client.ui.AbsolutePanel;
import com.google.gwt.user.client.ui.Image;
import com.google.gwt.user.client.ui.Grid;
//import java.math.BigInteger;
//import com.googlecode.gwt.math.Math;
import com.google.gwt.user.client.Random;

class BigInt
{
	public transient static final BigInt ZERO = new BigInt((byte)0);
	public transient static final BigInt ONE = new BigInt((byte)1);
	public transient static final BigInt TWO = new BigInt((byte)2);

	private byte[] m_bytes;
	private boolean m_sign;

	private BigInt(int size)
	{
		m_bytes = new byte[size];
	}

	public BigInt(byte n)
	{
		m_sign = true;
		m_bytes = new byte[1];
		m_bytes[0] = (byte)n;
	}

	public BigInt(byte[] arr)
	{
		m_sign = true;
		m_bytes = new byte[arr.length];
		for(int i = 0; i < m_bytes.length; i++)
			m_bytes[i] = arr[i];
	}

	public BigInt(String s)
	{
		if(s.length() < 1)
			throw new IllegalArgumentException("empty string");
		int start = 0;
		if(s.charAt(0) == '-')
		{
			m_sign = false;
			start++;
		}
		else
			m_sign = true;
		m_bytes = new byte[(s.length() - start + 1) / 2];
		for(int i = 0; i < m_bytes.length; i++)
			m_bytes[i] = 0;
		int pos = 0;
		for(int i = s.length() - 1; i >= start; i--)
		{
			int v;
			if(s.charAt(i) >= '0' && s.charAt(i) <= '9')
				v = (int)(s.charAt(i) - '0');
			else if(s.charAt(i) >= 'a' && s.charAt(i) <= 'f')
				v = (int)(s.charAt(i) - 'a' + 10);
			else if(s.charAt(i) >= 'A' && s.charAt(i) <= 'F')
				v = (int)(s.charAt(i) - 'A' + 10);
			else
				throw new IllegalArgumentException("invalid hexadecimal char");
			if((pos & 1) == 1)
				v = (v << 4);
			m_bytes[pos / 2] = (byte)((0xff & m_bytes[pos / 2]) | v);
			pos++;
		}
	}

	public BigInt clone()
	{
		BigInt other = new BigInt(bytes());
		for(int i = 0; i < other.m_bytes.length; i++)
			other.m_bytes[i] = m_bytes[i];
		other.m_sign = m_sign;
		return other;
	}

	public int bytes()
	{
		int n = m_bytes.length;
		while(n > 1 && m_bytes[n - 1] == 0)
			n--;
		return n;
	}

	private void clear()
	{
		m_sign = true;
		for(int i = 0; i < m_bytes.length; i++)
			m_bytes[i] = 0;
	}

	private void addInt(int value, int pos)
	{
		while(value > 0)
		{
			value += (0xff & m_bytes[pos]);
			m_bytes[pos] = (byte)value;
			pos++;
			value = value / 256;
		}
	}

	public BigInt multiply(BigInt other)
	{
		int n1 = bytes();
		int n2 = other.bytes();
		BigInt target = new BigInt(n1 + n2);
		target.clear();
		for(int j = 0; j < n2; j++)
		{
			for(int i = 0; i < n1; i++)
			{
				int n = (0xff & m_bytes[i]) * (0xff & other.m_bytes[j]);
				target.addInt(n, j + i);
			}
		}
		target.m_sign = !(m_sign ^ other.m_sign);
		return target;
	}

	public BigInt add(BigInt other)
	{
		if(m_sign && !other.m_sign)
		{
			other.m_sign = true;
			BigInt result = subtract(other);
			other.m_sign = false;
			return result;
		}
		if(!m_sign && other.m_sign)
		{
			m_sign = true;
			BigInt result = subtract(other);
			result.m_sign = !result.m_sign;
			m_sign = false;
			return result;
		}

		int n1 = bytes();
		int n2 = other.bytes();
		if(n1 >= n2)
		{
			BigInt target = new BigInt(n1 + 1);
			target.clear();
			for(int i = 0; i < n1; i++)
			{
				int n = (0xff & m_bytes[i]) + (i < n2 ? (0xff & other.m_bytes[i]) : 0);
				target.addInt(n, i);
			}
			target.m_sign = m_sign;
			return target;
		}
		else
		{
			BigInt target = new BigInt(n2 + 1);
			target.clear();
			for(int i = 0; i < n2; i++)
			{
				int n = (0xff &other.m_bytes[i]) + (i < n1 ? (0xff & m_bytes[i]) : 0);
				target.addInt(n, i);
			}
			target.m_sign = m_sign;
			return target;
		}
	}

	BigInt subtract(BigInt other)
	{
		if(!m_sign)
		{
			m_sign = true;
			BigInt result = add(other);
			m_sign = false;
			result.m_sign = !result.m_sign;
			return result;
		}
		if(!other.m_sign)
		{
			other.m_sign = true;
			BigInt result = add(other);
			other.m_sign = false;
			return result;
		}
		if(compareTo(other) < 0)
		{
			BigInt result = other.subtract(this);
			result.m_sign = !result.m_sign;
			return result;
		}

		// Subtract
		int n;
		int a;
		int b;
		boolean nextBorrow;
		boolean borrow = false;
		int byteCount = bytes();
		BigInt target = new BigInt(byteCount);
		target.clear();
		for(n = 0; n < byteCount; n++)
		{
			a = 0xff & m_bytes[n];
			b = 0xff & other.m_bytes[n];
			nextBorrow = false;
			if(borrow)
			{
				if(a == 0)
					nextBorrow = true;
				a--;
				a = (0xff & a);
			}
			if(b > a)
				nextBorrow = true;
			target.m_bytes[n] = (byte)(a - b);
			borrow = nextBorrow;
		}
		return target;
	}

	public int compareTo(BigInt other)
	{
		if(m_sign == other.m_sign)
		{
			int n1 = bytes();
			int n2 = other.bytes();
			if(n1 > n2)
				return (m_sign ? 1 : -1);
			if(n2 > n1)
				return (m_sign ? -1 : 1);
			for(int i = n1 - 1; i >= 0; i--)
			{
				if((0xff & m_bytes[i]) > (0xff & other.m_bytes[i]))
					return (m_sign ? 1 : -1);
				if((0xff & m_bytes[i]) < (0xff & other.m_bytes[i]))
					return (m_sign ? -1 : 1);
			}
			return 0;
		}
		else
		{
			if(m_sign)
			{
				int n1 = bytes();
				if(m_bytes[n1 - 1] != 0)
					return 1;
				int n2 = other.bytes();
				if(other.m_bytes[n2 - 1] != 0)
					return 1;
				return 0;
			}
			else
			{
				int n2 = other.bytes();
				if(other.m_bytes[n2 - 1] != 0)
					return -1;
				int n1 = bytes();
				if(m_bytes[n1 - 1] != 0)
					return -1;
				return 0;
			}
		}
	}

	public boolean equals(Object other)
	{
		return compareTo((BigInt)other) == 0;
	}

	private void shiftLeft()
	{
		byte[] input = m_bytes;
		if((0xff & m_bytes[m_bytes.length - 1]) >= 128)
		{
			input = m_bytes;
			m_bytes = new byte[m_bytes.length + 1];
			m_bytes[m_bytes.length - 1] = 1;
		}
		for(int i = input.length - 1; i > 0; i--)
			m_bytes[i] = (byte)((0xff & input[i]) * 2 | (input[i - 1] < 0 ? 1 : 0));
		m_bytes[0] = (byte)((0xff & input[0]) * 2);
	}

	private void shiftRight()
	{
		for(int i = 0; i < m_bytes.length - 1; i++)
			m_bytes[i] = (byte)((0xff & m_bytes[i]) / 2 | ((m_bytes[i + 1] & 1) * 128));
		m_bytes[m_bytes.length - 1] = (byte)((0xff & m_bytes[m_bytes.length - 1]) / 2);
	}

	private void setLSB(boolean bit)
	{
		if(bit)
			m_bytes[0] = (byte)((0xff & m_bytes[0]) | 1);
		else
			m_bytes[0] = (byte)((0xff & m_bytes[0]) & 254);
	}

	public int bits()
	{
		int n = bytes();
		int mask = 0x80;
		int b = (0xff & m_bytes[n - 1]);
		int i = 0;
		while(i < 8)
		{
			if((b & mask) > 0)
				break;
			i++;
			mask = (mask / 2);
		}
		return n * 8 - i;
	}

	public boolean getBit(int index)
	{
		int byt = index / 8;
		int bit = index % 8;
		return (((0xff & m_bytes[byt]) & (1 << bit)) > 0);
	}

	public BigInt divide(BigInt denominator)
	{
		int n1 = bytes();
		int n2 = denominator.bytes();
		BigInt target = new BigInt(n1);
		target.clear();
		BigInt remainder = new BigInt(n2 + 1);
		remainder.clear();
		int bitCount = bits();
		for(int n = 0; n < bitCount; n++)
		{
			remainder.shiftLeft();
			remainder.setLSB(getBit(bitCount - 1 - n));
//Window.alert("1 tar=" + target + " rem=" + remainder);
			target.shiftLeft();
			if(remainder.compareTo(denominator) >= 0)
			{
				target.setLSB(true);
				remainder = remainder.subtract(denominator);
			}
			else
				target.setLSB(false);
//Window.alert("2 tar=" + target + " rem=" + remainder);
		}
		return target;
	}

	public BigInt modulus(BigInt denominator)
	{
		int n1 = bytes();
		int n2 = denominator.bytes();
		BigInt remainder = new BigInt(n2 + 1);
		remainder.clear();
		int bitCount = bits();
		for(int n = 0; n < bitCount; n++)
		{
			remainder.shiftLeft();
			remainder.setLSB(getBit(bitCount - 1 - n));
			if(remainder.compareTo(denominator) >= 0)
				remainder = remainder.subtract(denominator);
		}
		return remainder;
	}

	private boolean millerRabin(BigInt a)
	{
		if(!getBit(0))
			return false; // this is an even number
		BigInt g = a.gcd(this);
		if(g.compareTo(BigInt.ONE) > 0)
			return false; // this has a common divisor with a
		BigInt m = subtract(BigInt.ONE);
		int s = 0;
		while(!m.getBit(0))
		{
			m.shiftRight();
			s++;
		}
		BigInt b = a.modPow(m, this);
		if(b.compareTo(BigInt.ONE) == 0)
			return true;
		if(b.add(BigInt.ONE).compareTo(this) == 0)
			return true;
		int i = 1;
		while(i < s)
		{
			m = b.multiply(b);
			BigInt b1 = m.modulus(this);
			if(b1.add(BigInt.ONE).compareTo(this) == 0)
				return true;
			if(b1.compareTo(BigInt.ONE) == 0)
				return false;
			b = b1;
			i++;
		}
		return false;
	}

	public static void shuffleEntropy(byte[] arr)
	{
		for(int i = arr.length; i > 1; i--)
		{
				int r = Random.nextInt(i);
				byte t = arr[r];
				arr[r] = arr[i - 1];
				arr[i - 1] = t;
		}
		if(arr.length < 14 && Random.nextInt(1 << (arr.length - 1)) == 0)
			arr[0] = (byte)((0xff & arr[0]) + 1);
	}

	private void makeWeakRandomForIsProbablePrime()
	{
		m_sign = true;
		for(int i = 0; i < m_bytes.length; i++)
			m_bytes[i] = (byte)Random.nextInt(256);
		if(compareTo(BigInt.ONE) <= 0)
			m_bytes[0] = (byte)(Random.nextInt(254) + 2);
	}
/*
	public boolean isProbablePrime(int certainty)
	{
		BigInt a = new BigInt(bytes() - 1);
		for(int i = 0; i < certainty; i++)
		{
			a.makeWeakRandomForIsProbablePrime();
			if(!millerRabin(a))
				return false;
		}
		return true;
	}
*/
	public static BigInt makePrime(byte[] entropy, int certainty)
	{
		PrimeMaker pm = BigInt.ZERO.new PrimeMaker(entropy, certainty);
		while(!pm.crunch())
		{
		}
		return pm.getResults();
	}

	public String toHexadecimal()
	{
		String s = (m_sign ? "" : "-");
		for(int i = m_bytes.length - 1; i >= 0; i--)
		{
			int msn = (0xf0 & m_bytes[i]) >> 4;
			s += (char)(msn >= 10 ? ('a' + msn - 10) : ('0' + msn));
			int lsn = 0x0f & m_bytes[i];
			s += (char)(lsn >= 10 ? ('a' + lsn - 10) : ('0' + lsn));
		}
		return s;
	}

	public String toString()
	{
		return toHexadecimal();
	}

	public BigInt gcd(BigInt val)
	{
		BigInt a = this;
		while(val.compareTo(BigInt.ZERO) != 0)
		{
			BigInt t = val;
			val = a.modulus(val);
			a = t;
		}
		return a;
	}

	public BigInt modInverse(BigInt m)
	{
		BigInt d = this;
		BigInt d2 = m;
		BigInt u = BigInt.ONE;
		BigInt u2 = BigInt.ZERO;
//		BigInt v = BigInt.ZERO;
//		BigInt v2 = BigInt.ONE;
		while(d2.compareTo(BigInt.ZERO) != 0)
		{
			BigInt q = d.divide(d2);
			BigInt t;
			t = d;
			d = d2;
			d2 = t.subtract(d2.multiply(q));
			t = u;
			u = u2;
			u2 = t.subtract(u2.multiply(q));
//			t = v;
//			v = v2;
//			v2 = t.subtract(v2.multiply(q));
		}
		if(!u.m_sign)
			u = u.add(m);
		return u;
	}

	public byte[] toByteArray()
	{
		byte[] arr = new byte[bytes()];
		for(int i = 0; i < arr.length; i++)
			arr[i] = m_bytes[i];
		return arr;
	}

	public BigInt modPow(BigInt exponent, BigInt m)
	{
		BigInt b = this;
		BigInt e = exponent.clone();
		BigInt r = BigInt.ONE;
		while(e.compareTo(BigInt.ZERO) > 0)
		{
			if(e.getBit(0))
				r = (r.multiply(b)).modulus(m);
			e.shiftRight();
			b = (b.multiply(b)).modulus(m);
		}
		return r;
	}

	public class PrimeMaker
	{
		private byte[] m_entropy;
		private int m_certainty;
		private BigInt m_cand;
		private BigInt m_t;
		private BigInt m_a;
		private int m_state;

		PrimeMaker(byte[] entropy, int certainty)
		{
			m_entropy = entropy;
			m_certainty = certainty;
			m_t = new BigInt((byte)3);
			m_state = 0;
		}

		private boolean isDivisibleBy(int n)
		{
			m_t.m_bytes[0] = (byte)n;
			if(m_cand.modulus(m_t).equals(BigInt.ZERO))
				return true;
			return false;
		}

		private boolean isPseudoPrime()
		{
			if(isDivisibleBy(3)) return false;
			if(isDivisibleBy(5)) return false;
			if(isDivisibleBy(7)) return false;
			if(isDivisibleBy(11)) return false;
			if(isDivisibleBy(13)) return false;
			if(isDivisibleBy(17)) return false;
			if(isDivisibleBy(19)) return false;
			if(isDivisibleBy(23)) return false;
			if(isDivisibleBy(29)) return false;
			if(isDivisibleBy(31)) return false;
			if(isDivisibleBy(37)) return false;
			if(isDivisibleBy(41)) return false;
			if(isDivisibleBy(43)) return false;
			if(isDivisibleBy(47)) return false;
			if(isDivisibleBy(53)) return false;
			if(isDivisibleBy(59)) return false;
			if(isDivisibleBy(61)) return false;
			return true;
		}

		boolean crunch()
		{
			if(m_state == 0)
			{
				shuffleEntropy(m_entropy);
				m_cand = new BigInt(m_entropy);
				if(!m_cand.getBit(0))
					m_cand.addInt(1, 0);
				m_state = 1;
			}
			if(m_state == 1)
			{
				for(int i = 0; i < 1; i++)
				{
					if(isPseudoPrime())
					{
						m_state = 2;
						m_a = new BigInt(m_cand.bytes() - 1);
						return false;
					}
					else
						m_cand.addInt(2, 0);
				}
				return false;
			}
			for(int i = 0; i < 1 && m_state < m_certainty; i++)
			{
				m_a.makeWeakRandomForIsProbablePrime();
				if(m_cand.millerRabin(m_a))
					m_state++;
				else
				{
					m_state = 0;
					return false;
				}
			}
			if(m_state < m_certainty)
				return false;
			return true;
		}

		public BigInt getResults()
		{
			return m_cand;
		}
	}
}
